package backTrack;

import java.util.*;

/**
 * 回溯算法，不要想太多，单层循环，每次逗趣一个数字里面的字母
 * 多个集和中选择
 */

public class ds17 {
    public static void main(String[] args) {
        System.out.println(letterCombinations("23"));
    }
    static String[] map = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public static List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        List<Character> path = new ArrayList<>();
        if(digits.length() == 0 || digits == null)
            return ans;
        char[] ch = digits.toCharArray();
        dfs(ch, ans, path, 0);
        return ans;
    }
    public static void dfs(char[] digits, List<String> ans, List<Character> path, int index){
        if(path.size() > digits.length)
            return;
        if(path.size() == digits.length){
            StringBuilder stringBuilder = new StringBuilder();
            for (char c : path) {
                stringBuilder.append(c);
            }
            ans.add(stringBuilder.toString());
            return;
        }
        int t = digits[index] - '0';
        for (int j = 0; j < map[t - 2].length(); j++) {
            path.add(map[t - 2].toCharArray()[j]);
            dfs(digits, ans, path, index + 1);
            path.remove(path.size() - 1);
        }
    }
}
